package slidingwindow;

import java.util.Arrays;
import java.util.TreeMap;

public class _1438_绝对差不超过限制的最长连续子数组 {

    /**
     * 给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
     *
     * 如果不存在满足条件的子数组，则返回 0 。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param nums
     * @param limit
     * @return
     *
     */
    public static int longestSubarray(int[] nums, int limit) {
        int left = 0, right = 0, max = 0;
        TreeMap<Integer, Integer> m = new TreeMap<>();
        while (right<nums.length){
            m.put(nums[right], m.getOrDefault(nums[right],0)+1);
            while (m.lastKey() - m.firstKey() > limit){
                m.put(nums[left], m.get(nums[left]) - 1);
                if(m.get(nums[left]) == 0){
                    m.remove(nums[left]);
                }
                left++;
            }
            max = Math.max(max, right- left +1);
            right++;
        }
        return max;
    }

    public static void main(String[] args) {
        int i = longestSubarray(new int[]{8, 2, 4, 7}, 4);
    }
}
